package com.wjk.test;

/**
 * @author : RobertWei
 * time: 2021/9/23    17:59
 * description:
 */

public class Demo {

    public static void main(String[] args) {

        ListNode listNode = detectCycle(new ListNode(2));
        System.out.println(listNode.val);

    }

    public static ListNode detectCycle(ListNode head) {

        //如果链表第一个或者第二个为空 直接返回空
        if (head == null || head.next == null) {
            return null;
        }

        //快慢指针
        ListNode fast = head;
        ListNode slow = head;

        while (fast != null) {

            //慢指针走一步
            slow = slow.next;

            //快指针下一个指向空 , 说明走到尽头 , 链表无循环 , 返回null
            if (fast.next == null) {
                return null;
            }
            //快指针走两步
            fast = fast.next.next;

            //快慢指针相遇, 说明有环
            if (fast == slow) {
                //此时将慢指针回归首位 , 并和快指针同时移动
                slow = head;
                while (slow != fast) {
                    slow = slow.next;
                    fast = fast.next;
                }
                return slow;
            }

        }
        //退出循环 证明 fast 指针走到链表末尾
        return null;
    }


}

class ListNode {

    int val;
    ListNode next;

    ListNode(int val) {
        this.val = val;
        next = null;
    }

}